class Solution {
public:
    vector<vector<string>> all_sol;
    unordered_set<int> n_set, sum_set, sub_set;

    void SetInsert(int i, int j) {
        n_set.insert(j);
        sum_set.insert(i + j);
        sub_set.insert(i - j);
    }

    void SetErase(int i, int j) {
        n_set.erase(j);
        sum_set.erase(i + j);
        sub_set.erase(i - j);
    }
    
    void _solveNQueens(vector<string>& sol, int cur, int n) {
        if (cur == n) {
            all_sol.push_back(sol);
            return;
        }

        for (int i = 0; i < n; i++) {
            if (n_set.count(i) || sum_set.count(i + cur) || sub_set.count(cur - i)) {
                continue;
            }
            string str(n, '.'); str[i] = 'Q';
            sol.push_back(move(str));
            SetInsert(cur, i);
            _solveNQueens(sol, cur + 1, n);
            sol.pop_back();
            SetErase(cur, i);
        }
    }
    vector<vector<string>> solveNQueens(int n) {
        vector<string> sol;
        _solveNQueens(sol, 0, n);
        return all_sol;
    }
};
